// 2025/4/3
// https://leetcode.cn/problems/next-permutation/?envType=study-plan-v2&envId=top-100-liked
// 下一个排列

class Solution {
    public:
        void nextPermutation(vector<int>& nums) {
            int n = nums.size(), cur = n - 2;
            while(cur >= 0 && nums[cur] >= nums[cur + 1])
                cur--;
            
            auto low = nums.begin();
            if(cur >= 0)
            {
                int fir = n - 1;
                while(nums[fir] <= nums[cur]) fir--;
                swap(nums[cur], nums[fir]);
                low += cur + 1;
            }
            reverse(low, nums.end());
        }
    };